package com.lw.leetcode.stack.b;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 1249. 移除无效的括号
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/20 17:11
 */
public class MinRemoveToMakeValid {

    public static void main(String[] args) {
        MinRemoveToMakeValid test = new MinRemoveToMakeValid();

        // "lee(t(co)de)" , "lee(t(c)ode)"
        String str = "lee(t(c)o)de)";

        // "ab(c)d"
//        String str = "a)b(c)d";

        // ""
//        String str = "))((";

        // "a(b(c)d)"
//        String str = "(a(b(c)d)";

        String s = test.minRemoveToMakeValid(str);
        System.out.println(s);
    }

    public String minRemoveToMakeValid(String s) {
        Set<Integer> set = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        int length = s.length();
        char[] chars = s.toCharArray();
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            if (c == '(') {
                stack.add(i);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    set.add(i);
                } else {
                    stack.pop();
                }
            }
        }
        while (!stack.isEmpty()) {
            set.add(stack.pop());
        }
        int i = 0;
        for (int j = 0; j < length; j++) {
            if (!set.contains(j)) {
                chars[i++] = chars[j];
            }
        }
        return String.valueOf(chars, 0, i);
    }


}
